googologywikiaorg-20200223-history
User blog:B1mb0w/Growth Rate of the S Function
'Growth Rate of the S Function' This blog will provide a detailed calculation and references for the growth rate of The S Function that I have developed. The growth rate is comparable to: \(S(n,T^{T(0)}(0),1) \approx f_{\varphi(1,1,0)}(n)\) 'Introduction' The S function is recursively defined set of two functions \(S()\) and \(T()\) which use string substitution procedures only. S Functions can be either restricted or generalised. Refer to my main blog on The S Function for a full definition of how the function is constructed. As a simple introduction it will be useful to compare a typical S function with more familiar functions: \(S(3,2,1) = f_2(3)\) ordinal value This equivalence is intentional. In fact: \(S(n,g,h) = f_g^h(n)\) ordinal value This equivalence will become more obvious if you refer to the definitions and rules for the function. I have intentionally defined The S Function to be a string substitution function with no explicit mathematical (e.g. algebraic) connotations. However the above equivalences will re-occur throughout the calculations. It is based on the definition that all restricted \(S()\) functions belong to a well-ordered sequence and every individual restricted \(S()\) function will have an assigned ordinal value equivalent to the result of the equivalent FGH function. In the case above; \(S(3,2,1)\) has the ordinal value 24. The \(T()\) function can be compared to various ordinals. \(T(0) \omega\) The similarity is intentional. The generalised S Functions, the functions of the form \(S(T(0),g,h)\), are similar to the ordinals that arise from the various attempts to define an FGH of Omega function, therefore: \(S(T(0),0,1) \omega + 1\) \(S(T(0),1,1) \omega.2\) The similarities are intentional. However, the similarity fades as we examine larger and larger inputs to the \(T()\) function. We can now start calculating the Growth Rate of the restricted S Function. 'Summary of Growth Rate Calculations' Here is a summary of the Growth Rate Calculations that are explained in more detail in the following sections: \(S(n,T(0),1) = f_{\omega}(n)\) \(S(n,S(T(0),0,1),1) = f_{\omega + 1}(n)\) \(S(n,S(T(0),1,1),1) = f_{\omega.2}(n)\) \(S(n,S(T(0),2,1),1) > f_{\omega^2}(n)\) \(S(n,S(T(0),2,2),1) > f_{\omega\uparrow\uparrow 2}(n)\) \(S(n,S(T(0),3,1),1) > f_{\omega\uparrow\uparrow n}(n) = f_{\varphi(1,0)}(n) = f_{\epsilon_0}(n) = f_{\psi(0)}(n)\) \(S(n,S(T(0),4,1),1) > f_{\varphi(2,0)}(n) = f_{\zeta_0}(n) = f_{\psi(\Omega)}(n)\) \(S(n,S(T(0),5,1),1) > f_{\varphi(3,0)}(n) = f_{\psi(\Omega^2)}(n)\) \(S(n,S(T(0),m,1),1) > f_{\varphi(m-2,0)}(n)\) \(S(n,T(1),1) \approx f_{\varphi(\omega,0)}(n)\) \(S(n,T(2),1) > f_{\varphi^2(1_*,0)}(n) = f_{\varphi(\varphi(1,0),0)}(n)\) \(S(n,T(3),1) > f_{\varphi^3(1_*,0)}(n)\) \(S(n,T(m),1) > f_{\varphi^m(1_*,0)}(n)\) \(S(n,T(T(0)),1) > f_{\varphi(1,0,0)}(n)\) \(S(n,T(S(T(0),0,T(0)),1) > f_{\varphi(1,0,1)}(n)\) \(S(n,T^3(0),1) > f_{\varphi^2(1,0,0_*)}(n)\) \(S(n,T^m(0),1) > f_{\varphi^{m-1}(1,0,0_*)}(n)\) \(S(n,T^{T(0)}(0),1) \approx f_{\varphi(1,1,0)}(n)\) 'Summary of General Results' Here is a summary of some general results. Refer to the detailed calculations below for more information: \(S(n,S(T(0),m,1),1) > f_{\varphi(m-2,0)}(n)\) \(S(T(0),m,1) > \varphi(m-2,0)\) \(S(\beta,m,T(0)) > \varphi(m-1,\beta + 1)\) where \(\beta >= \varphi(m,0)\) \(S(\beta,m,T(0)) > \varphi(m-1,\gamma + 1)\) where \(\beta = \varphi(m-1,\gamma)\) \(S(\beta,m,T(0)) > \varphi(m-1,0)\) where \(\beta < \varphi(m-1,0)\) \(S(n,T(m),1) > f_{\varphi^m(1_*,0)}(n)\) \(T(m + 1) > \varphi(T(m),0)\) \(T(m) > \varphi^m(1_*,0)\) \(S(n,T(T(0)),1) > f_{\varphi(1,0,0)}(n)\) \(T(T(0)) > \varphi(1,0,0)\) \(S(\beta,T(T(0)),1) > \varphi(1,0,\beta + 1)\) where \(\beta >= \varphi(1,1,0)\) \(S(\beta,T(T(0)),1) > \varphi(1,0,\gamma + 1)\) where \(\beta = \varphi(1,0,\gamma)\) \(S(\beta,T(T(0)),1) > \varphi(1,0,0)\) where \(\beta < \varphi(1,0,0)\) \(T(\beta) \approx \varphi(1,0,\beta + 1)\) where \(\beta >= \varphi(1,1,0)\) \(T(\beta) \approx \varphi(1,0,\beta)\) where \(\beta >= \varphi(1,0,0)\) 'Growth Rate up to \(S(n,T(0),1)\)' All restricted S Functions belong to a well-ordered sequence and every individual restricted \(S()\) function will have an assigned ordinal value. By definition: \(S(0,0,0) = 0 = 0\) \(S(1,0,0) = 1 = 1\) \(S(n,0,0) = n = n\) \(S(n,g,h) = f_g^h(n)\) Therefore the Growth Rate of the S Function up to \(S(n,g,h)\) where \(g\) is a finite integer, grows at a rate comparable to \(f_{\omega}^h(n)\), and no additional proof should be required. In fact: \(S(n,T(0),1) = f_{\omega}(n)\) 'Growth Rate up to \(S(n,S(T(0),2,2),1)\)' Also refer to the various blogs for an FGH of Omega function to calculate the growth rate of The S Function: \(S(n,S(T(0),1,1),1) = f_{\omega.2}(n)\) \(S(n,S(S(T(0),1,1),0,1),1) = f_{\omega.2 + 1}(n)\) \(S(n,S(S(T(0),1,1),0,T(0)),1) = f_{\omega.2 + n}(n) = f_{\omega.3}(n)\) \(S(n,S(S(T(0),1,1),0,S(T(0),1,1)),1) = S(n,S(T(0),1,2),1) = f_{\omega.2 + \omega.2}(n) = f_{\omega.4}(n)\) \(S(n,S(T(0),2,1),1) > f_{\omega.\omega}(n) = f_{\omega^2}(n)\) and \(S(n,S(T(0),2,2),1) = S(n,S(S(T(0),2,1),1,S(T(0),2,1)),1) >> f_{\omega^{\omega}}(n)\) because \(S(n,S(T(0),2,2),1) > f_{\omega^2.2^{\omega^2}}(n) > f_{\omega^{\omega}}(n)\) where \(n^2.2^{n^2} > 2^{n^2} = 2^{n.n} = (2^n)^n > n^n\) 'Growth Rate up to \(S(n,S(T(0),3,1),1)\)' From here we can show: \(S(n,S(T(0),2,3),1) = S(n,S(S(T(0),2,2),1,S(T(0),2,2)),1) >> f_{\omega\uparrow\uparrow 3}(n)\) because \(n^2.2^{n^2}.2^{n^2.2^{n^2}} > 2^{n^2.2^{n^2}} = 2^{n.n.2^{n.n}} = (2^{n.n})^{(2^n)^n} > n^{(2^n)^n} > n^{n^n} = n\uparrow\uparrow 3\) then \(S(n,S(T(0),2,m),1) > f_{\omega\uparrow\uparrow m}(n)\) \(S(n,S(T(0),2,m + 1),1) > f_{\omega\uparrow\uparrow (m + 1)}(n)\) until \(S(n,S(T(0),3,1),1) = S(n,S(T(0),2,T(0)),1) >> f_{\omega\uparrow\uparrow n}(n) = f_{\varphi(1,0)}(n) = f_{\epsilon_0}(n) = f_{\psi(0)}(n)\) Here are some examples of this equality: \(S(2,S(T(0),3,1),1) > S(2,S(T(0),1,1),1) = f_{\omega.2}(2) = f_{\omega^2}(2) = f_{\epsilon_0}(2)\) \(S(3,S(T(0),3,1),1) = S(3,T(1),1) > f_{\varphi(1,0)}(3) = f_{\epsilon_0}(3) = f_{\psi(0)}(3)\) \(S(4,S(T(0),3,1),1) > f_{\varphi(1,0)}(4) = f_{\epsilon_0}(4) = f_{\psi(0)}(4)\) 'Growth Rate up to \(S(n,S(T(0),4,1),1)\)' \(S(n,S(T(0),3,1),1) > f_{\varphi(1,0)}(n)\) \(S(n,S(S(T(0),3,1),2,1),1) > f_{\varphi(1,0)^2}(n)\) then \(S(S(T(0),3,1),2,1) > \varphi(1,0)^2\) \(S(S(T(0),3,1),2,2) > \varphi(1,0)\uparrow\uparrow 2\) \(S(S(T(0),3,1),2,3) > \varphi(1,0)\uparrow\uparrow 3\) \(S(S(T(0),3,1),2,T(0)) > \varphi(1,1)\) \(S(S(T(0),3,1),2,S(T(0),1,1)) > \varphi(1,2)\) \(S(S(T(0),3,1),2,S(T(0),1,2)) > \varphi(1,4)\) \(S(S(T(0),3,1),2,S(T(0),2,1)) > \varphi(1,\omega^2)\) \(S(T(0),3,2) = S(S(T(0),3,1),2,S(T(0),3,1)) > \varphi(1,\varphi(1,0))\) \(S(S(T(0),3,2),2,T(0)) > \varphi(1,\varphi(1,0) + 1)\) \(S(S(T(0),3,2),2,S(T(0),2,1)) > \varphi(1,\varphi(1,0) + \omega^2)\) \(S(S(T(0),3,2),2,S(T(0),3,1)) > \varphi(1,\varphi(1,0) + \varphi(1,0))\) \(S(T(0),3,3) = S(S(T(0),3,2),2,S(T(0),3,2)) > \varphi(1,\varphi(1,0) + \varphi(1,\varphi(1,0)))\) \(> \varphi(1,\varphi(1,\varphi(1,0))) = \varphi^3(1,0_*)\) \(S(T(0),4,1) = S(T(0),3,T(0)) > \varphi^{\omega}(1,0_*) = \varphi(2,0)\) 'Growth Rate up to \(S(n,S(T(0),5,1),1)\)' \(S(S(T(0),4,1),2,T(0)) > \varphi(1,\varphi(2,0) + 1)\) \(S(S(T(0),4,1),2,S(T(0),1,1)) > \varphi(1,\varphi(2,0) + 2)\) \(S(S(T(0),4,1),2,S(T(0),1,2)) > \varphi(1,\varphi(2,0) + 4)\) \(S(S(T(0),4,1),2,S(T(0),2,1)) > \varphi(1,\varphi(2,0) + \omega^2)\) \(S(S(T(0),4,1),2,S(T(0),2,2)) > \varphi(1,\varphi(2,0) + \omega\uparrow\uparrow 2)\) \(S(S(T(0),4,1),2,S(T(0),3,1)) > \varphi(1,\varphi(2,0) + \varphi(1,0))\) \(S(S(T(0),4,1),3,1) =\) \(S(S(T(0),4,1),2,S(T(0),4,1)) > \varphi(1,\varphi(2,0).2)\) \(S(S(S(T(0),4,1),3,1),2,T(0)) > \varphi(1,\varphi(2,0).2 + 1)\) \(S(S(S(T(0),4,1),3,1),2,S(T(0),4,1)) > \varphi(1,\varphi(2,0).2 + \varphi(2,0))\) \(S(S(S(T(0),4,1),3,1),2,S(S(T(0),4,1),2,T(0)) > \varphi(1,\varphi(2,0).2 + \varphi(1,\varphi(2,0) + 1))\) \(S(S(T(0),4,1),3,2) =\) \(S(S(S(T(0),4,1),3,1),2,S(S(T(0),4,1),3,1) > \varphi(1,\varphi(2,0).2 + \varphi(1,\varphi(2,0).2))\) \(> \varphi(1,\varphi(1,\varphi(2,0)+1)) = \varphi^2(1,(\varphi(2,0)+1)_*)\) \(S(S(T(0),4,1),3,T(0)) = \varphi^{\omega}(1,(\varphi(2,0)+1)_*) = \varphi(2,1)\) \(S(S(T(0),4,1),3,S(T(0),1,1)) = \varphi(2,2)\) \(S(S(T(0),4,1),3,S(T(0),1,2)) = \varphi(2,4)\) \(S(S(T(0),4,1),3,S(T(0),2,1)) = \varphi(2,\omega^2)\) \(S(S(T(0),4,1),3,S(T(0),3,1)) = \varphi(2,\varphi(1,0))\) \(S(T(0),4,2) =\) \(S(S(T(0),4,1),3,S(T(0),4,1)) = \varphi(2,\varphi(2,0)) = \varphi^2(2,0_*)\) \(S(T(0),5,1) = S(T(0),4,T(0)) = \varphi^{\omega}(2,0_*) = \varphi(3,0)\) 'Growth Rate up to \(S(n,T(1),1)\)' \(T(1) = S(T(0),T(0),1)\) then \(S(3,T(1),1) = S(3,S(T(0),T(0),1),1) = S(3,S(T(0),3,1),1) > f_{\epsilon_0}(3) = f_{\varphi(1,0)}(3)\) \(S(4,T(1),1) = S(4,S(T(0),T(0),1),1) = S(4,S(T(0),4,1),1) > f_{\varphi(2,0)}(4)\) \(S(5,T(1),1) = S(5,S(T(0),T(0),1),1) = S(5,S(T(0),5,1),1) > f_{\varphi(3,0)}(5)\) and \(S(n,T(1),1) > f_{\varphi(n - 2,0)}(n)\) \(S(n,T(1),1) \approx f_{\varphi(\omega,0)}(n)\) because \(S(S(n,T(1),1),S(T(0),3,1),1) > f_{\varphi(1,0)}(f_{\varphi(n - 2,0)}(n))\) \(S(S(n,T(1),1),S(T(0),n,1),1) > f_{\varphi(n - 2,0)}(f_{\varphi(n - 2,0)}(n)) = f^2_{\varphi(n - 2,0)}(n)\) \(S(S(n,T(1),1),S(T(0),S(n,0,1),1),1) > f_{\varphi(n - 1,0)}(n + 1)\) \(S(S(n,T(1),1),S(T(0),S(n,0,2),1),1) > f_{\varphi(n,0)}(n + 2) > f_{\varphi(n,0)}(n) = f_{\varphi(\omega,0)}(n)\) \(S(S(n,T(1),1),S(T(0),S(n,0,3),1),1) > f_{\varphi(\omega,0)}(n + 1)\) \(S(S(n,T(1),1),S(T(0),S(n,1,1),1),1) > f_{\varphi(\omega,0)}(n.2)\) \(S(S(n,T(1),1),S(T(0),S(n,2,1),1),1) > f_{\varphi(\omega,0)}(n^2)\) \(S(S(n,T(1),1),S(T(0),S(n,3,1),1),1) > f_{\varphi(\omega,0)}(f_3(n))\) \(S(S(n,T(1),1),S(T(0),S(n,T(0),1),1),1) > f_{\varphi(\omega,0)}(f_{\omega}(n))\) \(S(S(n,T(1),1),S(T(0),S(n,S(T(0),1,1),1),1),1) > f_{\varphi(\omega,0)}(f_{\omega.2}(n))\) \(S(S(n,T(1),1),S(T(0),S(n,S(T(0),2,1),1),1),1) > f_{\varphi(\omega,0)}(f_{\omega^2}(n))\) \(S(S(n,T(1),1),S(T(0),S(n,S(T(0),3,1),1),1),1) > f_{\varphi(\omega,0)}(f_{\varphi(1,0)}(n))\) \(S(n,T(1),2) = S(S(n,T(1),1),T(1),1) = S(S(n,T(1),1),S(T(0),T(0),1),1) =\) \(S(S(n,T(1),1),S(T(0),S(n,S(T(0),T(0),1),1),1),1) > f_{\varphi(\omega,0)}(f_{\varphi(n - 2,0)}(n))\) \(\approx f^2_{\varphi(\omega,0)}(n)\) \(S(n,S(T(1),0,1),1) = S(n,T(1),n) \approx f^n_{\varphi(\omega,0)}(n) = f_{\varphi(\omega,0) + 1}(n)\) 'Growth Rate up to \(S(n,T(2),1)\)' \(T(2) = S(T(1),T(1),1)\) then \(S(T(1),0,1) \approx \varphi(\omega,0) + 1\) \(S(T(1),1,1) \approx \varphi(\omega,0).2\) \(S(T(1),2,1) > \varphi(\omega,0)^2\) \(S(T(1),2,T(0)) > \varphi(1,\varphi(\omega,0) + 1)\) \(S(T(1),2,S(T(0),1,1)) > \varphi(1,\varphi(\omega,0) + 2)\) \(S(T(1),2,S(T(0),1,2)) > \varphi(1,\varphi(\omega,0) + 4)\) \(S(T(1),2,S(T(0),2,1)) > \varphi(1,\varphi(\omega,0) + \omega^2)\) \(S(T(1),2,S(T(0),3,1)) > \varphi(1,\varphi(\omega,0) + \varphi(1,0))\) \(S(T(1),3,1) = S(T(1),2,T(1)) = \) \(S(T(1),2,S(T(0),T(0),1)) \approx \varphi(1,\varphi(\omega,0).2)\) \(S(S(T(1),3,1),2,T(0)) > \varphi(1,\varphi(\omega,0).2 + 1)\) \(S(T(1),3,2) = \) \(S(S(T(1),3,1),2,S(T(1),3,1)) > \varphi(1,\varphi(\omega,0).2 + \varphi(1,\varphi(\omega,0).2))\) \(> \varphi(1,\varphi(1,\varphi(\omega,0) + 1)) = \varphi^2(1,(\varphi(\omega,0) + 1)_*)\) \(S(T(1),3,T(0)) > \varphi^{\omega}(1,(\varphi(\omega,0) + 1)_*) = \varphi(2,\varphi(\omega,0) + 1)\) \(S(T(1),4,T(0)) > \varphi(3,\varphi(\omega,0) + 1)\) \(S(T(1),T(0),T(0)) \approx \varphi(\omega,1)\) \(S(T(1),S(T(0),0,1),1) \approx \varphi(\omega + 1,0)\) \(S(T(1),S(T(0),1,1),1) \approx \varphi(\omega.2,0)\) \(S(T(1),S(T(0),2,1),1) > \varphi(\omega^2,0)\) \(S(T(1),S(T(0),3,1),1) > \varphi(\varphi(1,0),0)\) \(T(2) = S(T(1),T(1),1) = \) \(S(T(1),S(T(0),T(0),1),1) \approx \varphi(\varphi(\omega,0),0) = \varphi^2(\omega_*,0)\) 'Growth Rate up to \(S(n,T(T(0)),1)\)' \(T(m + 1) = S(T(m),T(m),1)\) then \(T(3) = S(T(2),T(2),1) \approx \varphi^3(\omega_*,0)\) \(T(m) \approx \varphi^m(\omega_*,0)\) \(T(T(0)) \approx \varphi^{\omega}(\omega_*,0) = \varphi(1,0,0) = \Gamma_0\) 'Growth Rate up to \(S(n,T(S(T(0),0,1)),1)\)' \(S(T(T(0)),3,1) \approx \varphi(1,\Gamma_0 + 1)\) \(S(T(T(0)),T(0),1) \approx \varphi(\omega,\Gamma_0 + 1)\) \(S(T(T(0)),S(T(0),1,1),1) \approx \varphi(\omega.2,\Gamma_0 + 1)\) \(S(T(T(0)),S(T(0),2,1),1) \approx \varphi(\omega^2,\Gamma_0 + 1)\) \(S(T(T(0)),S(T(0),3,1),1) \approx \varphi(\varphi(1,0),\Gamma_0 + 1)\) \(S(T(T(0)),T(1),1) \approx \varphi(\varphi(\omega,0),\Gamma_0 + 1)\) \(S(T(T(0)),T(2),1) \approx \varphi(\varphi^2(\omega_*,0),\Gamma_0 + 1)\) \(T(S(T(0),0,1)) = \) \(S(T(T(0)),T(T(0)),1) \approx \varphi(\varphi(1,0,0) + 1,\varphi(1,0,0) + 1)\) 'Growth Rate up to \(S(n,T^3(0),1)\)' \(T(m + 1) > \varphi(T(m),0)\) \(T(S(T(0),0,2)) > \varphi^2((\varphi(1,0,0) + 1)_*,0)\) \(T(S(T(0),0,3)) > \varphi^3((\varphi(1,0,0) + 1)_*,0)\) \(T(S(T(0),1,1)) = \) \(T(S(T(0),0,T(0)) > \varphi^n((\varphi(1,0,0) + 1)_*,0) = \varphi(1,0,1)\) \(T(S(T(0),1,2)) > \varphi(1,0,3)\) \(T(S(T(0),2,1)) > \varphi(1,0,\omega^2)\) \(T(S(T(0),3,1)) > \varphi(1,0,\varphi(1,0))\) \(T(T(1)) = T(S(T(0),T(0),1)) \approx \varphi(1,0,\varphi(\omega,0))\) \(T(\beta) > \varphi(1,0,\beta)\) \(T(T(2)) > \varphi(1,0,\varphi^2(\omega_*,0))\) \(T(T(m)) > \varphi(1,0,\varphi^m(\omega_*,0))\) \(T^3(0) = T(T(T(0))) > \varphi(1,0,\varphi(1,0,0)) = \varphi^2(1,0,0_*)\) 'Growth Rate up to \(S(n,T^{T(0)}(0),1)\)' \(T(\beta) > \varphi(1,0,\beta)\) \(T^4(0) > \varphi^3(1,0,0_*)\) \(T^m(0) > \varphi^{m - 1}(1,0,0_*)\) \(T^{T(0)}(0) \approx \varphi^{\omega}(1,0,0_*) = \varphi(1,1,0)\) 'Alternative Calculations of \(S()\) Growth Rates' I tried some alternative calculations but have since given up on them. The following blogs are no longer relevant: *Comparing T() Functions to Ordinals *Omega Count 'Further References' Further references to relevant blogs can be found here: User:B1mb0w Category:Blog posts